UVa/11394 - Digit Blocks/robado.cpp

   1 //Este código produce TLE
   2 //Robado de http://online-judge.uva.es/board/viewtopic.php?t=27307&start=15
   3 //By arsalan_mousavian
   4
   5 #include <iostream>
   6 #include <algorithm>
   7 #include <memory>
   8 #include <vector>
   9 #include <cstdio>
  10 #include <utility>
  11 #include <fstream>
  12 #include <string>
  13
  14 using namespace std;
  15 #define ll long long
  16 ll dp [1<<16][5] ;
  17 char input [20];
  18
  19 inline int value ( char ch){
  20    if ( isalpha ( ch ) ) return 10 + ch - 'A';
  21    return ch - '0';
  22 }
  23
  24 int main (){
  25    while ( cin >> input ){
  26       if ( !strcmp ( input , "#") ) break ;
  27
  28       int n = strlen ( input ) ;
  29       sort ( input , input + n ) ;
  30       for (register int mask = 0 ; mask < (1<<n) ; mask ++ ){
  31          for ( int mod = 0 ; mod < 5 ; mod ++ ){
  32             if ( mask == 0 ) dp [mask][mod] = 0 ;
  33             else{
  34                dp [mask][mod] = 0 ;
  35                int prev = -1 ;
  36                for ( int i=0 ; i<n  ; i++ ){
  37                   if ( mask & ( 1<<i ) ){
  38                      int next = 0 ;
  39                      int cur = value ( input [i] );
  40                      if ( prev == cur ) continue ;
  41                      prev = cur ;
  42                      next = ( 500 + mod - cur ) % 5;
  43                      if ( next == 0 ) dp [mask][mod] ++ ;
  44                      dp[mask][mod] += dp[mask - (1<<i)][next];
  45                   }
  46                }
  47             }
  48             if ( mask == (1<<n) - 1 && mod == 0 )
  49                break ;
  50          }
  51       }
  52       cout << dp [(1<<n)-1][0] << endl;
  53    }
  54 }